|
A polyphase merge sort is an algorithm which decreases the number of ''runs'' at every iteration of the main loop by merging runs into larger runs. It is used for external sorting. ==Ordinary merge sort== Typically, a merge sort splits items into sorted runs and then recursively merges each run into larger runs. When there's only one run left, that is the sorted result. An ordinary merge sort could use four working files organized as a pair of input files and a pair of output files. At each iteration, two input files are read. The odd numbered runs of the two input files are merged to the first output file, and the even numbered runs are merged to the second output file. When the input is exhausted, the new output files are used as the input for the next iteration. The number of runs decreases by a factor of 2 at each iteration. At each iteration, the same level/phase of merge occurs—a file is either completely read or completely written during an iteration. If the four files were on four separate tape drives, watching an ordinary merge sort would show some interesting details. On the first iteration, only one input drive is used—the other input file is empty. On subsequent iterations, each input drive runs at half speed,〔The two input drives are throttled by the output drive's speed. They cannot provide data faster than the output drive can write it.〕 while one output drive runs at full speed and the second output drive stands idle waiting for the next run. The situation is even worse when six tape drives are used—at least two will stand idle. Someone watching the tapes spin would wonder if the idle drives could be more useful. The polyphase merge found a way to use the idle drives. It can sort using just three sequential files rather than the four required by merge sort. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Polyphase merge sort」の詳細全文を読む スポンサード リンク
|